| 翻訳と辞書 |
| Tutte–Coxeter graph ： ウィキペディア英語版 |
Tutte–Coxeter graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8 it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle ''W''2 (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a).
All the cubic distance-regular graphs are known.〔Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.〕 The Tutte–Coxeter is one of the 13 such graphs.
== Constructions and automorphisms ==
A particularly simple combinatorial construction of the Tutte–Coxeter graph is due to Coxeter (1958b), based on work by Sylvester (1844). In modern terminology, take a complete graph on 6 vertices ''K''6. It has 15 edges. There are 15 ways to choose 3 disjoint edges (that is, 15 perfect matchings of ''K''6). Create a graph with 30 vertices corresponding to the 15 edges and the 15 perfect matchings, with an edge from each perfect matching to each of its three edges. That is the Tutte-Coxeter graph.
Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph; it has a group of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six vertices of the K6 graph; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the outer automorphisms of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte–Coxeter graph is equivalent to any other such path by one such automorphism.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Tutte–Coxeter graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|